package com.ds.tree;

import java.util.ArrayList;
import java.util.List;

public class BinaryTree<T extends Comparable<? super T>> {

	private BinaryNode<T> root;
	
	public void addNode(T t) {
		
		BinaryNode<T> node = new BinaryNode<T>(t);
		
		root = insert(t,root);
		
	}
	
	private BinaryNode<T> insert(T t,BinaryNode<T> node) {
		
		if(node == null) {
			return new BinaryNode<T>(t);
		}
		int result = t.compareTo(node.t);
			
		if(result < 0) {
			node.left = insert(t,node.left);
		}else if(result > 0) {
			node.right = insert(t,node.right);
		}
		return node;
	}
	
	public BinaryNode<T> delete(T t) {
		
		return delete(t,root);
	}
	
	private BinaryNode<T> delete(T t,BinaryNode<T> node) {
		
		if(node == null) {
			return node;
		}
		
		int result = t.compareTo(node.t);
		
		if(result > 0) {
			node.right = delete(t,node.right);
		}else if(result < 0){
			node.left = delete(t,node.left);
		}else {
			if(node.left == null || node.right == null) {
				node = (node.left != null)? node.left : node.right;
			}else {
				node.t = getMin(node.right);
				node.right = delete(node.t,node.right);
			}
		}
		return node;
	}
		
	
	public BinaryNode<T> get(T t) {
		
		BinaryNode<T> node = root;
		
		while(node != null) {
			
			if(t.compareTo(node.t) == 0) {
				return node;
			}else if(t.compareTo(node.t) < 0) {
				node = node.left;
			}else {
				node = node.right;
			}
		}
		return null;
		
	}
	
	public List<T> getAll(){
		List<T> itemList = new ArrayList<T>();
		getAll(root,itemList);
		
		return itemList;
	}
	
	private void getAll(BinaryNode<T> node,List<T> list){
		
		if(node == null) {
			return;
		}
		getAll(node.left,list);
		list.add(node.t);
		getAll(node.right,list);
		
	}
	
	public T getMax() {
		return getMax(root);
	}
	
	private T getMax(BinaryNode<T> node) {
		
		while(node.right != null) {
			node = node.right;
		}
		return node.t;
		
	}
	
	public T getMin() {
		return getMin(root);
	}
	
	private T getMin(BinaryNode<T> node) {
		while(node.left != null) {
			node = node.left;
		}
		return node.t;
	}
	
	public void showTree() {
		
		showNode(root,"");
	}
	
	public void showNode(BinaryNode<T> node,String depstr) {
		
		if(node == null) {
			return;
		}
		
		int dep = depstr.length();
		
		for(int i = 0; i < dep ; i++) {
			if(i != dep - 1) {
				if("1".equals(depstr.substring(i,i+1))){
					System.out.print("│  ");
				}else {
					System.out.print("   ");
				}
			}else {
				if("1".equals(depstr.substring(i,i+1))){
					System.out.print("├─");
				}else {
					System.out.print("└─");
				}
			}
		}
		System.out.println(node.t);	
		String flag = "0";
		if(node.right != null) {
			flag = "1";
		}
		showNode(node.left,depstr + flag);
		showNode(node.right,depstr + "0");
	}
}
